package euler.p001_050;

import java.math.BigInteger;

import euler.MainEuler;

public class Euler025 extends MainEuler {

    /*
        The Fibonacci sequence is defined by the recurrence relation:

            Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

        Hence the first 12 terms will be:

            F1 = 1
            F2 = 1
            F3 = 2
            F4 = 3
            F5 = 5
            F6 = 8
            F7 = 13
            F8 = 21
            F9 = 34
            F10 = 55
            F11 = 89
            F12 = 144

        The 12th term, F12, is the first term to contain three digits.

        What is the first term in the Fibonacci sequence to contain 1000 digits?

     */
	public String resolve(int limite) {
		BigInteger digitsMinus1 = BigInteger.TEN.pow(limite - 1).subtract(BigInteger.ONE);

		BigInteger fn_2 = BigInteger.ONE;
		BigInteger fn_1 = BigInteger.ONE;
		BigInteger fn = BigInteger.ZERO;

		int i = 2;

		while (fn.compareTo(digitsMinus1) <= 0) {
			i++;
			fn = fn_1.add(fn_2);
			fn_2 = fn_1;
			fn_1 = fn;
		}

		return String.valueOf(i);
	}
}
